package leetcode_121_140;

import RandomList.Node;

import java.util.HashMap;

public class copyRandomList_138 {
    /**
     * 随机链表的深拷贝
     */
    public Node copyRandomList(Node head) {
        /**
         * 思路是利用hash表存储节点之间的关系
         * 0ms
         */
        if(head==null)
            return null;

        HashMap<Node,Node>map=new HashMap<>();  //key是原节点，value是拷贝节点
        Node root=head;

        //确定新随机链表的头节点
        Node newHead=new Node(root.val);
        map.put(root,newHead);
        root=root.next;
        Node root1=newHead;

        //顺序遍历确定次序关系，拷贝所有已有节点，保存原节点和新节点的对应关系
        while(root!=null){
            Node copy=new Node(root.val); //拷贝节点
            root1.next=copy;   //确立次序

            map.put(root,copy); //记录对应关系

            root=root.next;
            root1=root1.next;
        }

        //通过直接的map关系,填充random指针
        Node root2=head;
        while(root2!=null){
            if (root2.random != null)
                map.get(root2).random = map.get(root2.random);
            //map.get(root2)即当前需要填充random指针的节点
            //map.get(root2)需要填充 （root2的random指针指向的节点）在map中所对应的节点，即 map.get(root2.random)
            root2 = root2.next;
        }
        return newHead;
    }
}
